package com.github.yangyishe.p100;

/**
 * 50. Pow(x, n)
 * https://leetcode.cn/problems/powx-n/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：x = 2.00000, n = 10
 * 输出：1024.00000
 * 示例 2：
 *
 * 输入：x = 2.10000, n = 3
 * 输出：9.26100
 * 示例 3：
 *
 * 输入：x = 2.00000, n = -2
 * 输出：0.25000
 * 解释：2-2 = 1/22 = 1/4 = 0.25
 *
 *
 * 提示：
 *
 * -100.0 < x < 100.0
 * -231 <= n <= 231-1
 * n 是一个整数
 * 要么 x 不为零，要么 n > 0 。
 * -104 <= xn <= 104
 */
public class Problem50 {
    public static void main(String[] args) {
        double x=2.00000;
        int n=-2147483648;

        Problem50 problem50 = new Problem50();
        double pow = problem50.myPow(x, n);
        System.out.println("pow = " + pow);

    }

    /**
     * 思路:
     * 暂不考虑误差问题和溢出问题
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        // 对n进行分层考虑
        //1. 如果n>0
        if(n>0){
            return positivePow(x,n);
        }

        //2. 如果n==0
        if(n==0){
            return 1;
        }

        //3. 如果n<0. 将原来的公式x^n=(1/x)^(-n)

        if(n==Integer.MIN_VALUE){
            // 溢出考虑
            return positivePow(1/x,Integer.MAX_VALUE)*(1/x);
        }

        return positivePow(1/x,-n);
    }


    private double positivePow(double x,int n){
        // 当n>0时
        // 暴力算法, 就是对n个x进行相乘,
        // 但时间复杂度过大, 可考虑将n解析为一个二进制数, 如13=0b1101, 则结果=result+result^4+result^8
        double result=1;
        double temp=x;
        while(n>0){
            if((n&1)!=0){
                result*=temp;
            }
            temp=temp*temp;
            n>>=1;
        }

        return result;
    }
}
